package org.chengn.level_middle.context1038;

import org.chengn.definition.TreeNode;

public class Context1038 {
    public TreeNode bstToGst(TreeNode root) {
        dfs(root, 0);
        return root;
    }

    public int dfs(TreeNode root, int sum) {
        if (root == null) return sum;
        if (root.left == null && root.right == null) {
            int val = sum + root.val;
            return root.val = val;
        }
        int sumR = dfs(root.right, sum);
        int sumMid = root.val + sumR;
        root.val = sumMid;
        return dfs(root.left, sumMid);

    }
}
